20. Valid Parentheses(Easy)

题目描述

原题

Description:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: “()”

Output: true

Example 2:

Input: “()[]{}”

Output: true

Example 3:

Input: “(]”

Output: false

Example 4:

Input: “([)]”

Output: false

Example 5:

Input: “{[]}”

Output: true

原题翻译

描述：

给定一个String字符串，其只包含以下字符：'(', ')', '{', '}', '[' and ']'，判断该字符串是否有效.

若一个字符串有效，则:

1. 开括号必须用相同类型的括号封闭。
2. 开括号必须以正确的顺序关闭。

请注意，空字符串也被视为有效。

例1：

输入： “()”

输出： true

例2：

输入： “()[]{}”

输出： true

例3：

输入： “(]”

输出： false

例4：

输入： “([)]”

输出： false

例5：

输入： “{[]}”

输出： true

解法一（mine）

主要思想

1. 定义一个栈，遍历s对应的char数组放入栈中.

2. 遇到右括号，弹出栈顶元素，若不是对应的左括号，返回false。

运行速度：超过了98.71%的解答。

内存使用：超过了100%的解答。

源码

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == ')') {
                if(stack.empty() || stack.pop() != '(')
                    return false;
            } else if (c == '}') {
                if(stack.empty() || stack.pop() != '{')
                    return false;
            } else if (c == ']') {
                if(stack.empty() || stack.pop() != '[')
                    return false;
            } else {
                stack.add(c);
            }
        }
        return stack.empty();
    }
}